package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}21:29
 */
public class LeetCode105 {

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0){
            return null;
        }
        return help(preorder,0,preorder.length-1,inorder,0,inorder.length - 1);
    }

    public TreeNode help(int[] preorder,int pstart,int pend,int[] inorder,int istart,int iend){
        if (pstart > pend || istart > iend){
            return null;
        }
        TreeNode node = new TreeNode(preorder[pstart]);

        //计算相位差
        int index = 0;
        while (inorder[index+istart] != preorder[index]){
            index++;
        }
        node.left = help(preorder,pstart+1,pstart+index,inorder,istart+1,istart+index-1);
        node.right = help(preorder,pstart+index+1,pend,inorder,istart+index+1,iend);
        return node;
    }
}
